package puzzle.projecteuler.p100;

/**
 * 1x1 + 2x2 + 5x3 + 10x4 + 20x5 + 50x6 + 100x7 + 200x8 = 200 
 * @author Administrator
 *
 */
public class Problem031 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int[] p = {1,2,5,10,20,50,100,200};
		int max = 200;
		System.out.println(s(max, p));
	}
	
	/**
	 * 
	 * @param max
	 * @param p 		in ascending order
	 * @return
	 */
	public static int s(int max, int[] p) {
		
		if (p.length == 1) {
			return (max%p[0] == 0)?1:0;
		} else {
			int m = p[p.length-1];
			int x = max/m;
			int[] newP = new int[p.length-1]; 
			System.arraycopy(p, 0, newP, 0, p.length-1);
			int c = 0;
			for (int i = 0; i <= x; i ++) {
				c += s(max-m*i, newP);
			}
			return c;
		}
	}
}
